package demo1;
import java.util.*;
public class Solution {
    //1.剑指 Offer 10- I. 斐波那契数列(动态规划)
    public int fib(int n) {
        //转移方程:f[n] = f[n - 1] + f[n - 2];
        //初始化
        int[] arr = new int[n + 1];
        if(n < 2) {
            return n;
        }
        arr[0] = 0;
        arr[1] = 1;
        for(int i = 2; i <= n; i++) {
            arr[i] = (arr[i - 1] + arr[i - 2]) % (1000000007);
        }
        return arr[n];
    }
    //1.剑指 Offer 10- I. 斐波那契数列(动态规划优化空间复杂度O(1))
//    public int fib(int n) {
//        //转移方程:f[n] = f[n - 1] + f[n - 2];
//        //初始化
//        if(n < 2) {
//            return n;
//        }
//        int a = 0;
//        int b = 1;
//        int sum = 0;
//        for(int i = 2; i <= n; i++) {
//            sum = (a + b) % 1000000007;
//            a = b;
//            b = sum;
//        }
//        return sum;
//    }
    //2.剑指 Offer 10- II. 青蛙跳台阶问题(动态规划,优化版)
    public int numWays(int n) {// 1111 112 211 121 22
        //f(1) = 1,f(2) = 2,f(3) = f(2) + f(1) = 3;
        //f(4) = f(2) + f(3) = 5
        //转移方程:f(n) = f(n - 1) + f(n - 2);
        //初始化f(1) = 1,f(2) = 2;
        if(n == 0) {
            return 1;
        }
        if(n <= 2) {
            return n;
        }
        int f1 = 1;
        int f2 = 2;
        int ret = 0;
        for(int i = 3; i <= n; i++) {
            ret = (f1 + f2) % 1000000007;
            f1 = f2;
            f2 = ret;
        }
        return ret;
    }
    //3.剑指 Offer 14- I. 剪绳子(动态规划)
    public int cuttingRope(int n) {
        //f(i)表示i被分成j和i - j，后的最大乘积
        //i < 2时，f(0) = 0;f(1) = 0;
        //i > 2时:假设拆出来的第一个数是j;
        //不可再继续分割:f(i) = j * (i - j)
        //可以再继续分割:f(i) = j * f(i - j)
        //状态方程:f(i) = Math.max(j*(i - j), j * f(i - j));
        int[] dp = new int[n + 1];
        for(int i = 2; i <= n; i++) {//表示绳子的长度
            for(int j = 1; j < i; j++) {
                dp[i] = Math.max(dp[i], Math.max(j*(i - j), j*(dp[i - j])));
            }
        }
        return dp[n];
    }
    //4。跳台阶扩展问题(动态规划)
    public int jumpFloorII (int number) {
        //动态规划
        //f(n)表示青蛙跳到该台阶的跳法
        //假设第一次跳1个台阶，就剩下n-1个台阶,假设第一次跳2个台阶，就剩下n-2个台阶
        //转移方程:f(i) = f(i - 1) + f(i - 2) + ... + f(1) + f(0);
        if(number <= 2) {
            return number;
        }
        int[] dp = new int[number + 1];
        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 2;
        for(int i = 3; i <= number; i++) {
            for(int j = 0; j < i; j++) {
                dp[i] += dp[j];
            }
        }
        return dp[number];
    }
    //5.爬楼梯(动态规划优化)
    public int climbStairs(int n) {
        //只有两种方法：
        //一、第一次上一步
        //二、第一次上两步
        //状态转移方程:f(i) = f(i - 1) + f(i - 2);
        if(n <= 2) {
            return n;
        }
        int a = 1;
        int b = 2;
        int ret = 0;
        for(int i = 3; i <= n; i++) {
            ret = a + b;
            a = b;
            b = ret;
        }
        return ret;
    }
    //6.使用最小花费爬楼梯(动态规划)
    public int minCostClimbingStairs(int[] cost) {
        int len = cost.length;
        int[] dp = new int[len];
        dp[0] = 0;
        dp[1] = Math.min(cost[0], cost[1]);
        for(int i = 2; i < len; i++) {
            dp[i] = Math.min(dp[i - 1] + cost[i], dp[i - 2] + cost[i - 1]);
        }
        return dp[len - 1];
    }
    //7.柠檬水找零(贪心)
    public boolean lemonadeChange(int[] bills) {
        int m5 = 0;//5￥
        int m10 = 0;//10￥
        for(int i = 0; i < bills.length; i++) {
            if(bills[i] == 5) {
                m5++;
            }else if(bills[i] == 10) {
                if(m5 > 0) {//只要包里还有5美元，就可以成功归还
                    m5--;
                }else {
                    return false;
                }
                m10++;
            }else {
                if(m10 > 0 && m5 > 0) {//一个1元，一个5元
                    m10--;
                    m5--;
                }else if(m5 >= 3) {//三个5元也可以
                    m5 -= 3;
                }else {
                    return false;
                }
            }
        }
        return true;
    }
    //8.不同路径(动态规划)
    public int uniquePaths(int m, int n) {
        //f[i][j]表示到达这里所走的所有方法
        //状态转移方程:f[i][j] = f[i - 1][j] + f[i][j - 1];
        //初始化
        //第一行：只有一条路径
        //第一列：只有一条路径
        int[][] dp = new int[m][n];
        for(int i = 0; i < n; i++) {
            dp[0][i] = 1;
        }
        for(int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        for(int i = 1; i < m; i++) {
            for(int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
    //9.不同路径 II
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int row = obstacleGrid.length;
        int line = obstacleGrid[0].length;
        int[][] dp = new int[row][line];
        for(int i = 0; i < line && obstacleGrid[0][i] == 0; i++) {
            dp[0][i] = 1;
        }
        for(int i = 0; i < row && obstacleGrid[i][0] == 0; i++) {
            dp[i][0] = 1;
        }
        for(int i = 1; i < row; i++) {
            for(int j = 1; j < line; j++){
                if(obstacleGrid[i][j] == 0) {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[row - 1][line - 1];
    }
    //10.剑指 Offer 47. 礼物的最大价值(动态规划)
    public int maxValue(int[][] grid) {
        int row = grid.length;
        int line = grid[0].length;
        int[][] dp = new int[row][line];
        //第一行
        for(int i = 0; i < line; i++) {
            if(i == 0) {
                dp[0][i] = grid[0][i];
            }else {
                dp[0][i] = grid[0][i] + dp[0][i - 1];
            }
        }
        //第一列
        for(int i = 0; i < row; i++) {
            if(i == 0) {
                dp[i][0] = grid[i][0];
            }else {
                dp[i][0] = grid[i][0] + dp[i - 1][0];
            }
        }
        for(int i = 1; i < row; i++) {
            for(int j = 1; j < line; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }
        return dp[row - 1][line - 1];
    }
    //最小路径和(动态规划)
    public int minPathSum(int[][] grid) {
        int row = grid.length;
        int line = grid[0].length;
        int[][] dp = new int[row][line];
        //第一行
        for(int i = 0; i < line; i++) {
            if(i == 0) {
                dp[0][i] = grid[0][i];
            }else {
                dp[0][i] = grid[0][i] + dp[0][i - 1];
            }
        }
        //第一列
        for(int j = 0; j < row; j++) {
            if(j == 0) {
                dp[j][0] = grid[j][0];
            }else {
                dp[j][0] = grid[j][0] + dp[j - 1][0];
            }
        }
        for(int i = 1; i < row; i++) {
            for(int j = 1; j < line; j++){
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }
        return dp[row - 1][line - 1];
    }

    public int minimumTotal(List<List<Integer>> triangle) {
        int row = triangle.size();//行
        //第一列
        for(int i = 1; i < row; i++) {
            triangle.get(i).set(0,
                    triangle.get(i - 1).get(0) + triangle.get(i).get(0));
        }
        //斜列
        for(int i = 1; i < row; i++) {
            for(int j = 1; j < triangle.get(i).size(); j++) {
                if(i == j) {
                    triangle.get(i).set(j,
                            triangle.get(i - 1).get(j - 1) + triangle.get(i).get(j));
                }
            }
        }
        //剩下部分
        for(int i = 2; i < row - 1; i++) {
            for(int j = 1; j < triangle.get(i).size() - 1; j++) {
                triangle.get(i).set(j,
                        Math.min(triangle.get(i - 1).get(j),
                                triangle.get(i - 1).get(j - 1)) + triangle.get(i).get(j));
            }
        }
        return triangle.get(row - 1).get(triangle.get(row - 1).size() - 1);
    }
    //三角形最小路径和(动态规划——自下而上)
//    public int minimumTotal(List<List<Integer>> triangle) {
//        int n = triangle.size();
//        int[][] dp = new int[n + 1][n + 1];
//        //自下而上
//        for(int i = n - 1; i >= 0; i--) {
//            for(int j = 0; j <= i; j++) {
//                dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle.get(i).get(j);
//            }
//        }
//        return dp[0][0];
//    }
}
